package cn.javadog.algorithm.m1_100;


import java.util.HashMap;
import java.util.Map;

/**
 * 无重复字符的最长子串
 * https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
 * @author Sprite
 */
public class Algorithm3 {
	public static void main(String[] args) {
		System.out.println(lengthOfLongestSubstring("abcabcbb"));
		System.out.println(lengthOfLongestSubstring("bbbbb"));
		System.out.println(lengthOfLongestSubstring("pwwkew"));
		System.out.println(lengthOfLongestSubstring("au"));
		System.out.println(lengthOfLongestSubstring("aau"));
	}

	public static int lengthOfLongestSubstring(String s) {
		if (s.length() == 0) return 0;

		char[] chars = s.toCharArray();
		Map<Character,Integer> map = new HashMap<>();
		int max = 1;
		int start = -1;
		for (int i = 0; i < chars.length; i++) {
			char c = chars[i];
			if (map.containsKey(c)){
				Integer idx = map.get(c);
				if (idx > start){
					max = Math.max(max, i-idx);
					start = idx;
				}else {
					max = Math.max(max,i-start);
				}
			}else {
				max = Math.max(max,i-start);
			}
			map.put(c,i);
		}


		return max;
	}
}
